#include <iostream>
using namespace std;
int findMidValue(int arr[], int L, int R, int mid)
{
	if ((arr[L] >= arr[R] && arr[L] <= arr[mid])|| (arr[L] <= arr[R] && arr[L] >= arr[mid]))
	{
		return L;
	}
	if ((arr[R] >= arr[L] && arr[R] <= arr[mid])|| (arr[R] <= arr[L] && arr[R] >= arr[mid]))
	{
		return R;
	}
	if ((arr[mid] >= arr[R] && arr[mid] <= arr[L])|| (arr[mid] <= arr[R] && arr[mid] >= arr[L]))
	{
		return mid;
	}
}
void quickSort(int arr[], int L, int R)
{
	if (L > R)return;
	int mid = L + ((R - L) >> 1);
	int ret = findMidValue(arr, L, R, mid);
	int pivot = arr[ret];
	int left = L;
	int right = R;
	while (left <= right)
	{
		while (left <= right && arr[left] <= pivot)
		{
			left++;
		}
		while (left <= right && arr[right] >= pivot)
		{
			right--;
		}
		if (left <= right)
		{
			int tmp = arr[left];
			arr[left] = arr[right];
			arr[right] = tmp;
		}
	}
	int tmp = arr[ret];
	arr[ret] = arr[right];
	arr[right] = tmp;
	quickSort(arr, L, right - 1);
	quickSort(arr, right + 1, R);
}
int main()
{
	int arr[] = { 78,56,34,43,4,1,15,2,23 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	quickSort(arr, 0, sz - 1);
	for (int i = 0; i < sz; i++)
	{
		cout << arr[i] << " ";
	}
}